#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int word_len = words[0].size();
        unordered_map<string, int> target;
        for (auto& str : words) target[str]++;
        vector<int> res;
        for (int start = 0; start < word_len; start++)
        {
            unordered_map<string, int> hash;
            int left = start;
            for (int right = start; right < s.size(); right += word_len)
            {
                string str = s.substr(right, word_len);
                ++hash[str];
                while (hash[str] > target[str])
                {
                    string left_str = s.substr(left, word_len);
                    --hash[left_str];
                    left += word_len;
                }
                if (right - left == (word_len * (words.size() - 1)))
                    res.push_back(left);
            }
        }
        return res;
    }
};